package Text25;

import java.util.*;

public class Main {
    //    给定 n个正整数，将它们分组，使得每组中任意两个数互质。
//    至少要分成多少个组？
    static int N = 15, n;
    static int[] p = new int[N];
    static int[][] group = new int[N][N];
    static boolean[] st = new boolean[N];
    static int ans = N;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for (int i = 0; i < n; i++) {
            p[i] = in.nextInt();
        }
        dfs(1, 0, 0, 0);
        System.out.println(ans);
    }

    private static void dfs(int g, int gc, int cnt, int start) {
        if (g >= ans) {
            return;
        }
        if (cnt == n) {
            ans = g;
        }
        boolean falg = true;
        for (int i = start; i < n; i++) {
            if (!st[i] && check(group[g], i, gc)) {
                st[i] = true;
                group[g][gc] = i;
                dfs(g, gc + 1, cnt + 1, i + 1);
                st[i] = false;
                falg = false;
            }
        }
        if (falg) {
            dfs(g + 1, 0, cnt, 0);
        }
    }

    private static boolean check(int[] g, int u, int gc) {
        for (int i = 0; i < gc; i++) {
            if (gcd(p[g[i]], p[u]) > 1) {
                return false;
            }
        }
        return true;
    }

    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}
